/**
 * @param {number[][]} triangle
 * @return {number}
 */

var minimumTotal = function (triangle) {
    let row = triangle.length
    let min = Infinity
    // 初始化最小值
    let dp = new Array(row + 1).fill(Infinity)
    for (let i = 0; i <= row; i++) {
        dp[i] = new Array(triangle[row - 1].length + 1).fill(Infinity)
    }
    dp[0][0] = dp[0][1] = 0
    // 进行相加 动态规划 dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle[i - 1][j - 1]
    for (let i = 1; i <= row; i++) {
        for (let j = 1; j <= triangle[i - 1].length; j++) {
            dp[i][j] = 0
            if (!triangle[i - 1][j - 1]) {
                triangle[i - 1][j - 1] = 0
            }
            dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i - 1][j - 1]
        }
    }
    // 筛选出最后一行最小的数
    for (let i = 0; i < dp[0].length; i++) {
        if (dp[row][i] < min) {
            min = dp[row][i]
        }
    }
    return min
};
minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])